//
// Created by bleedingfight on 2020/6/30.
//
#include "maxProductCutting.h"
#include <iostream>
int maxProductCutting(int n) {
    if (n <= 3)
        return n - 1;
    int nums = n / 3;
    int res = n % 3;
    if (res == 0)
        return pow(3, nums);
    else if (res == 1)
        return pow(3, nums - 1) * 4;
    else
        return 2 * pow(3, nums);
}

int maxProductCutting1(int n, std::vector<int> &cache) {
    if (n <= 4)
        return n;
    int result = n;
    for (int i = 1; i <= n / 2; i++) {
        if (cache[n - i] == 0)
            cache[n - i] = maxProductCutting1(n - i, cache);//
        if (cache[i] == 0)
            cache[i] = maxProductCutting1(i, cache);
        result = std::max(result, cache[i] * cache[n - i]);
    }
    return result;

}

int maxProductCutting1(int n) {
    if (n <= 3)
        return n - 1;
    else {
        std::vector<int> cache = std::vector<int>(n, 0);
        return maxProductCutting1(n, cache);
    }
}
int maxProductCutting2(int n){
    if(n==2)
        return 1;
    int result = -1;
    for(int i=1;i<n;i++)
        result = std::max(result,std::max(i*(maxProductCutting2(n-i)),i*(n-i)));
    return result;
}
int maxProductCutting3(int n,std::vector<int>&cache){
    if(n<=3)
        return n-1;
    int result = -1;
    std::vector<int>mid_result = std::vector<int>(4,0);
    for(int i=1;i<=n/2;i++){
        if(cache[i] == -1)
            cache[i] = maxProductCutting3(i,cache);
        if(cache[n-i] == -1)
            cache[n-i] = maxProductCutting3(n-i,cache);

//        std::cout<<"n="<<n<<" x:"<<i<<" n-x="<<n-i<<" x*(n-x)="<<i*(n-i)<<" f["<<i<<"]="<<cache[i]<<" f["<<n-i<<"]="<<cache[n-i]<<" Max result:"<<std::max(cache[i]*(cache[n-i]),i*(n-i))<<"\n";
        mid_result[0]=cache[i]*(cache[n-i]);
        mid_result[1]=cache[i]*(n-i);
        mid_result[2]=i*(cache[n-i]);
        mid_result[3]=i*(n-i);
//        std::cout<<"f(x)*f(n-x) = "<<mid_result[0]<<" f(x)*(n-x) = "<<mid_result[1]<<" x*f(x) = "<<mid_result[2]<<" i*(n-i) = "<<mid_result[3]<<"\n";
        result = std::max(result,*std::max_element(mid_result.begin(),mid_result.end()));
    }
    return result;
}
int maxProductCutting3(int n){
    std::vector<int>cache  = std::vector<int>(n,-1);
    return maxProductCutting3(n,cache);
}
